<!DOCTYPE html>



  


<html class="theme-next pisces use-motion" lang="zh-Hans">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>
<meta name="theme-color" content="#222">






  
  
  <link rel="stylesheet" media="all" href="/lib/Han/dist/han.min.css?v=3.3">




<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
















  
  
  <link href="/lib/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />







<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=5.1.3" rel="stylesheet" type="text/css" />


  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=5.1.3">


  <link rel="icon" type="image/png" sizes="32x32" href="/img/icon.png?v=5.1.3">


  <link rel="icon" type="image/png" sizes="16x16" href="/img/icon.png?v=5.1.3">


  <link rel="mask-icon" href="/images/logo.svg?v=5.1.3" color="#222">





  <meta name="keywords" content="cayun's blog, IT, ACM/ICPC, blog, cayun" />










<meta property="og:type" content="website">
<meta property="og:title" content="cayun&#39;s blog">
<meta property="og:url" content="http://localhost/page/2/index.html">
<meta property="og:site_name" content="cayun&#39;s blog">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="cayun&#39;s blog">



<script type="text/javascript" id="hexo.configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Pisces',
    version: '5.1.3',
    sidebar: {"position":"left","display":"post","offset":12,"b2t":true,"scrollpercent":true,"onmobile":false},
    fancybox: true,
    tabs: true,
    motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    duoshuo: {
      userId: '0',
      author: '博主'
    },
    algolia: {
      applicationID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    }
  };
</script>



  <link rel="canonical" href="http://localhost/page/2/"/>





  <title>cayun's blog</title>
  




<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
            (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
          m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','https://www.google-analytics.com/analytics.js','ga');
  ga('create', 'UA-93052608-1', 'auto');
  ga('send', 'pageview');
</script>


  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "https://hm.baidu.com/hm.js?1ca7c9c8011b37b0c209724dc77c24db";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">

  
  
    
  

  <div class="container sidebar-position-left 
  page-home">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta ">
    

    <div class="custom-logo-site-title">
      <a href="/"  class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">cayun's blog</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
      
        <h1 class="site-subtitle" itemprop="description">不积跬步, 无以至千里!</h1>
      
  </div>

  <div class="site-nav-toggle">
    <button>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />
            
            首页
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />
            
            关于
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-tags"></i> <br />
            
            标签
          </a>
        </li>
      
        
        <li class="menu-item menu-item-categories">
          <a href="/categories/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-th"></i> <br />
            
            分类
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives/" rel="section">
            
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />
            
            归档
          </a>
        </li>
      

      
    </ul>
  

  
</nav>



 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
  <section id="posts" class="posts-expand">
    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/hdu6085/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hdu6085/" itemprop="url">hdu 6085 Rikka with Candies (压位+位运算)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-08-08T00:00:00+08:00">
                2017-08-08
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/hdu6085/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/hdu6085/" class="cy_cmt_count" data-xid="hdu6085/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>首先把$A$数组映射到一个$bitset<em>{A}$中，答案数组也映射到一个$bitset</em>{ans}$中。</p>
<p>因为$i \bmod j = i - j \lfloor \frac{i}{j} \rfloor$，因此可以枚举$j$和$k=\lfloor \frac{i}{j} \rfloor$。其中$j \in B$。这时相当于把$bitset<em>{A}$中区间$[kj,(k+1)j)$中的所有数对应加到$bitset</em>{ans}$的$[0,j)$区间上。</p>
<p>因为模$2$意义下的加法就相当于异或。因此我们用压位来优化整个区间的加法。</p>
<p>因为bitset不支持区间提取，所以需要手写压位。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> M = <span class="number">4000</span>;</div><div class="line"><span class="keyword">unsigned</span> a[M], b[M];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">setA</span><span class="params">(<span class="keyword">int</span> p, <span class="keyword">int</span> x)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> p1 = p / <span class="number">32</span>, p2 = p % <span class="number">32</span>;</div><div class="line">    a[p1] |= (<span class="number">1</span> &lt;&lt; p2);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">getB</span><span class="params">(<span class="keyword">int</span> p)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> p1 = p / <span class="number">32</span>, p2 = p % <span class="number">32</span>;</div><div class="line">    <span class="keyword">return</span> (b[p1] &gt;&gt; p2) &amp; <span class="number">1</span>;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">myXor</span><span class="params">(<span class="keyword">int</span> p1, <span class="keyword">int</span> p2, <span class="keyword">int</span> len)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> pos1 = p1 / <span class="number">32</span>, pos2 = p2 / <span class="number">32</span>, flag = <span class="number">1</span>, left = <span class="number">32</span> - p1 % <span class="number">32</span>, right = p1 % <span class="number">32</span>;</div><div class="line">    <span class="keyword">while</span> (len &gt; <span class="number">0</span>) &#123;</div><div class="line">        <span class="keyword">if</span> (right == <span class="number">0</span>) &#123;</div><div class="line">            <span class="keyword">if</span> (len &gt;= <span class="number">32</span>) &#123;</div><div class="line">                b[pos2++] ^= a[pos1++];</div><div class="line">                len -= <span class="number">32</span>;</div><div class="line">            &#125; <span class="keyword">else</span> &#123;</div><div class="line">                b[pos2++] ^= ((a[pos1++] &lt;&lt; (<span class="number">32</span> - len)) &gt;&gt; (<span class="number">32</span> - len));</div><div class="line">                len -= len;</div><div class="line">            &#125;</div><div class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (flag == <span class="number">0</span>) &#123;</div><div class="line">            swap(left, right);</div><div class="line">            <span class="keyword">if</span> (right &lt;= len) &#123;</div><div class="line">                b[pos2++] ^= (a[pos1] &lt;&lt; left);</div><div class="line">                len -= right;</div><div class="line">            &#125; <span class="keyword">else</span> &#123;</div><div class="line">                b[pos2] ^= (a[pos1] &lt;&lt; (<span class="number">32</span> - len) &gt;&gt; (<span class="number">32</span> - len) &lt;&lt; left);</div><div class="line">                len -= len;</div><div class="line">            &#125;</div><div class="line">            flag = <span class="number">1</span>;</div><div class="line">        &#125; <span class="keyword">else</span> &#123;</div><div class="line">            swap(left, right);</div><div class="line">            <span class="keyword">if</span> (right &lt;= len) &#123;</div><div class="line">                b[pos2] ^= (a[pos1++] &gt;&gt; left);</div><div class="line">                len -= right;</div><div class="line">            &#125; <span class="keyword">else</span> &#123;</div><div class="line">                b[pos2] ^= (a[pos1] &gt;&gt; left &lt;&lt; (<span class="number">32</span> - len) &gt;&gt; (<span class="number">32</span> - len));</div><div class="line">                len -= len;</div><div class="line">            &#125;</div><div class="line">            flag = <span class="number">0</span>;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="built_in">memset</span>(a, <span class="number">0</span>, <span class="keyword">sizeof</span> a);</div><div class="line">    <span class="built_in">memset</span>(b, <span class="number">0</span>, <span class="keyword">sizeof</span> b);</div><div class="line">    <span class="keyword">int</span> n, m, q; <span class="built_in">scanf</span>(<span class="string">"%d%d%d"</span>, &amp;n, &amp;m, &amp;q);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        <span class="keyword">int</span> x; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;x);</div><div class="line">        setA(x, <span class="number">1</span>);</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= m; i++) &#123;</div><div class="line">        <span class="keyword">int</span> x; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;x);</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt;= <span class="number">50000</span>; j += x) &#123;</div><div class="line">            myXor(j, <span class="number">0</span>, min(x, <span class="number">50001</span> - j));</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; q; i++) &#123;</div><div class="line">        <span class="keyword">int</span> x; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;x);</div><div class="line">        <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, getB(x));</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> T; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;T);</div><div class="line">    <span class="keyword">while</span> (T--) solve();</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/hdu6090/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hdu6090/" itemprop="url">hdu 6090 Rikka with Graph (构造)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-08-08T00:00:00+08:00">
                2017-08-08
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/hdu6090/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/hdu6090/" class="cy_cmt_count" data-xid="hdu6090/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>一道简单的构造题。</p>
<p>我们先假设一个中心点，然后尽可能地将其他点与该点相连，如果还有多余的边，那么我们就将非中心点进行两两相连。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span> </span>&#123;</div><div class="line">    LL n, m; <span class="built_in">scanf</span>(<span class="string">"%lld%lld"</span>, &amp;n, &amp;m);</div><div class="line">    LL ans = <span class="number">0</span>;</div><div class="line">    <span class="keyword">if</span> (m &lt; n - <span class="number">1</span>) &#123;</div><div class="line">        <span class="keyword">if</span> (m == <span class="number">1</span>) &#123;</div><div class="line">            LL x = <span class="number">2</span>, y = n - <span class="number">2</span>;</div><div class="line">            ans += (<span class="number">1</span> + y * n) * <span class="number">2</span>;</div><div class="line">            ans += y * n * (n - <span class="number">1</span>);</div><div class="line">        &#125; <span class="keyword">else</span> &#123;</div><div class="line">            LL x = m + <span class="number">1</span>, y = n - x;</div><div class="line">            ans = (<span class="number">1</span> + <span class="number">2</span> * (x - <span class="number">2</span>) + y * n) * (x - <span class="number">1</span>);</div><div class="line">            ans += x - <span class="number">1</span> + y * n;</div><div class="line">            ans += y * n * (n - <span class="number">1</span>);</div><div class="line">        &#125;</div><div class="line">    &#125; <span class="keyword">else</span> <span class="keyword">if</span> (m &lt; n * (n - <span class="number">1</span>) / <span class="number">2</span>) &#123;</div><div class="line">        ans = n * (n - <span class="number">1</span>) + (n * (n - <span class="number">1</span>) / <span class="number">2</span> - m) * <span class="number">2</span>;</div><div class="line">    &#125; <span class="keyword">else</span> &#123;</div><div class="line">        ans = n * (n - <span class="number">1</span>);</div><div class="line">    &#125;</div><div class="line">    <span class="built_in">printf</span>(<span class="string">"%lld\n"</span>, ans);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> T; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;T);</div><div class="line">    <span class="keyword">while</span> (T--) solve();</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/hdu6065/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hdu6065/" itemprop="url">hdu 6065 RXD, tree and sequence (动态规划)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-08-07T00:00:00+08:00">
                2017-08-07
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/hdu6065/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/hdu6065/" class="cy_cmt_count" data-xid="hdu6065/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>题解见<a href="http://blog.csdn.net/qq_31759205/article/details/76696276" target="_blank" rel="external">十分残念的博客</a>。</p>
<p>讲讲我对最后一个式子的理解，$dp<em>{i,j} = \min {(dp</em>{i,j},dp<em>{i-2,j-1}+dep[LCA(a</em>{i-1},a_{i})])}$，对于第$i-2$个数，若它不是第$j-1$块的祖先，我们可以发现它在第$j-1$块和第$j$块对答案没有任何影响，若它是$j-1$堆的祖先，则放第$j-1$块。总而言之，无论哪种情况，第$i-2$个放$j-1$块都是没问题的。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">300010</span>;</div><div class="line"><span class="keyword">const</span> LL INF = <span class="number">0x3f3f3f3f3f3f3f3f</span>;</div><div class="line"><span class="keyword">int</span> a[N], dep[N];</div><div class="line"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; g[N];</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">ST</span> &#123;</span></div><div class="line">    <span class="keyword">enum</span> &#123;ST_SIZE = <span class="number">20</span>&#125;;</div><div class="line">    <span class="keyword">int</span> logTwo[N &lt;&lt; <span class="number">1</span>], st[N &lt;&lt; <span class="number">1</span>][ST_SIZE];</div><div class="line"></div><div class="line">    ST() &#123;</div><div class="line">        logTwo[<span class="number">0</span>] = <span class="number">-1</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; (N &lt;&lt; <span class="number">1</span>); i++) &#123;</div><div class="line">            logTwo[i] = ((i &amp; (i - <span class="number">1</span>)) == <span class="number">0</span>) ? logTwo[i<span class="number">-1</span>] + <span class="number">1</span> : logTwo[i<span class="number">-1</span>];</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">(<span class="keyword">int</span> *a, <span class="keyword">int</span> n)</span> </span>&#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) st[i][<span class="number">0</span>] = a[i];</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; ST_SIZE; j++)</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i + (<span class="number">1</span> &lt;&lt; j) &lt;= n + <span class="number">1</span>; i++) </div><div class="line">            st[i][j] = min(st[i][j<span class="number">-1</span>], st[i + (<span class="number">1</span> &lt;&lt; (j<span class="number">-1</span>))][j<span class="number">-1</span>]);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">query</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r)</span> </span>&#123;</div><div class="line">        <span class="keyword">int</span> k = logTwo[r-l+<span class="number">1</span>];</div><div class="line">        <span class="keyword">return</span> min(st[l][k], st[r+<span class="number">1</span>-(<span class="number">1</span>&lt;&lt;k)][k]);</div><div class="line">    &#125;</div><div class="line">&#125;st;</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">LCA</span> &#123;</span></div><div class="line">    <span class="keyword">int</span> p, m;</div><div class="line">    <span class="keyword">int</span> mp[N &lt;&lt; <span class="number">1</span>], val[N &lt;&lt; <span class="number">1</span>], first[N];</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">()</span> </span>&#123;</div><div class="line">        p = m = <span class="number">0</span>;</div><div class="line">        dfs(<span class="number">1</span>, <span class="number">0</span>, <span class="number">1</span>);</div><div class="line">        st.init(val, m);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> u, <span class="keyword">int</span> f, <span class="keyword">int</span> depth)</span> </span>&#123;</div><div class="line">        dep[u] = depth;</div><div class="line">        mp[++p] = u;</div><div class="line">        val[++m] = p;</div><div class="line">        first[u] = m;</div><div class="line">        <span class="keyword">int</span> t = p;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; g[u].size(); i++) &#123;</div><div class="line">            <span class="keyword">int</span> v = g[u][i];</div><div class="line">            <span class="keyword">if</span> (v == f) <span class="keyword">continue</span>;</div><div class="line">            dfs(v, u, depth + <span class="number">1</span>);</div><div class="line">            val[++m] = t;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">query</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b)</span> </span>&#123;</div><div class="line">        <span class="keyword">if</span> (first[a] &gt; first[b]) swap(a, b);</div><div class="line">        <span class="keyword">return</span> mp[st.query(first[a], first[b])];</div><div class="line">    &#125;</div><div class="line">&#125;lca;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) g[i].clear();</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">input</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;a[i]);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; n; i++) &#123;</div><div class="line">        <span class="keyword">int</span> u, v; <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;u, &amp;v);</div><div class="line">        g[u].push_back(v);</div><div class="line">        g[v].push_back(u);</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">(<span class="keyword">int</span> n, <span class="keyword">int</span> k)</span> </span>&#123;</div><div class="line">    init(n);</div><div class="line">    input(n);</div><div class="line">    lca.init();</div><div class="line"></div><div class="line">    LL **dp = <span class="keyword">new</span> LL*[n+<span class="number">1</span>];</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt;= n; i++) dp[i] = <span class="keyword">new</span> LL[k+<span class="number">1</span>];</div><div class="line"></div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt;= n; i++) </div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt;= k; j++)</div><div class="line">        dp[i][j] = j == <span class="number">0</span> ? <span class="number">0</span> : INF;</div><div class="line"></div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt;= k; j++) &#123;</div><div class="line">            dp[i][j] = min(dp[i<span class="number">-1</span>][j], dp[i<span class="number">-1</span>][j<span class="number">-1</span>] + dep[a[i]]);</div><div class="line">            <span class="keyword">if</span> (i &gt; <span class="number">1</span>) dp[i][j] = min(dp[i][j], dp[i<span class="number">-2</span>][j<span class="number">-1</span>] + dep[lca.query(a[i<span class="number">-1</span>], a[i])]);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="built_in">printf</span>(<span class="string">"%lld\n"</span>, dp[n][k]);</div><div class="line"></div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt;= n; i++) <span class="keyword">delete</span> [] dp[i];</div><div class="line">    <span class="keyword">delete</span> [] dp;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> n, k;</div><div class="line">    <span class="keyword">while</span> (<span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;n, &amp;k) != EOF) solve(n, k);</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/hdu6041/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hdu6041/" itemprop="url">hdu 6041 I Curse Myself (点双连通分量+K路合并)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-08-07T00:00:00+08:00">
                2017-08-07
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/hdu6041/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/hdu6041/" class="cy_cmt_count" data-xid="hdu6041/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>从题意中可以知道该图是一个仙人掌图，所以对于图上的每一个环都需要从环上取出一条边删掉。所以问题就变为了有M个集合，每个集合中都有一些数字，要从每个集合中各选择一个数加起来，求前K大。</p>
<p>于是就变成了K路合并问题，我们对这些集合两两合并即可。两个集合合并的过程如下，假设这两个集合分别为$a<em>{1..n}$和$b</em>{1..m}$，且$b$数组已经从大到小排好序了，为了维护整个操作，我们再开一个大根堆$heap$。接下来的步骤就是，首先将$a<em>{i} + b</em>{1}, i \in [1,n]$都放入$heap$中，那么我们每次都取$heap$中的最大值，对于当前次，不妨设取的数为$a<em>{i} + b</em>{j}$，那么我们取完后再将$a<em>{i} + b</em>{j+1}$插入$heap$中即可，直到取满$k$个数或$heap$为空。</p>
<p>需要注意的是，合并时需要使用启发式合并，即小的集合往大的集合去合并，不然会TLE。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">1005</span>;</div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> M = <span class="number">2005</span>;</div><div class="line"></div><div class="line"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; s[N];</div><div class="line"><span class="keyword">int</span> w[N][N], sumW, a[<span class="number">100010</span>], b[<span class="number">100010</span>];</div><div class="line"><span class="keyword">int</span> sn, an, bn;</div><div class="line"></div><div class="line"><span class="comment">//点双连通分量模板</span></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Edge</span> &#123;</span></div><div class="line">    <span class="keyword">int</span> v;</div><div class="line">    <span class="keyword">bool</span> bridge; <span class="comment">//是否为桥的标记</span></div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="keyword">int</span> low[N], dfn[N], index;</div><div class="line"><span class="keyword">int</span> edgeNum; <span class="comment">//边的数目</span></div><div class="line"><span class="keyword">int</span> block; <span class="comment">//边双连通块数</span></div><div class="line"><span class="keyword">int</span> belong[N]; <span class="comment">//属于第几块, 值为1-block</span></div><div class="line"><span class="keyword">int</span> bridge; <span class="comment">//桥的数目</span></div><div class="line"><span class="keyword">bool</span> inStack[N];</div><div class="line">Edge edge[M &lt;&lt; <span class="number">1</span>];</div><div class="line"><span class="built_in">stack</span>&lt;<span class="keyword">int</span>&gt; stk;</div><div class="line"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; g[N];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">initGraph</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</div><div class="line">    edgeNum = block = index = bridge = <span class="number">0</span>;</div><div class="line">    <span class="built_in">memset</span>(inStack, <span class="literal">false</span>, <span class="keyword">sizeof</span> inStack);</div><div class="line">    <span class="built_in">memset</span>(low, <span class="number">0</span>, <span class="keyword">sizeof</span> low);</div><div class="line">    <span class="built_in">memset</span>(dfn, <span class="number">0</span>, <span class="keyword">sizeof</span> dfn);</div><div class="line">    <span class="keyword">while</span> (!stk.empty()) stk.pop();</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) g[i].clear(); </div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">addEdge</span><span class="params">(<span class="keyword">int</span> u, <span class="keyword">int</span> v, <span class="keyword">int</span> ww)</span> </span>&#123;</div><div class="line">    edge[edgeNum].v = v; edge[edgeNum].bridge = <span class="literal">false</span>;</div><div class="line">    g[u].push_back(edgeNum++);</div><div class="line">    edge[edgeNum].v = u; edge[edgeNum].bridge = <span class="literal">false</span>;</div><div class="line">    g[v].push_back(edgeNum++);</div><div class="line">    w[u][v] = w[v][u] = ww;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">tarjan</span><span class="params">(<span class="keyword">int</span> u, <span class="keyword">int</span> father)</span> </span>&#123;</div><div class="line">    low[u] = dfn[u] = ++index;</div><div class="line">    stk.push(u);</div><div class="line">    inStack[u] = <span class="literal">true</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; g[u].size(); i++) &#123;</div><div class="line">        <span class="keyword">int</span> eid = g[u][i], v = edge[eid].v;</div><div class="line">        <span class="keyword">if</span> (v == father) <span class="keyword">continue</span>;</div><div class="line">        <span class="keyword">if</span> (dfn[v] == <span class="number">0</span>) &#123;</div><div class="line">            tarjan(v, u);</div><div class="line">            low[u] = min(low[u], low[v]);</div><div class="line">            <span class="keyword">if</span> (low[v] &gt;= dfn[u]) &#123;</div><div class="line">                block++; sn++;</div><div class="line">                <span class="keyword">int</span> vn, pre = u;</div><div class="line">                <span class="keyword">do</span> &#123;</div><div class="line">                    vn = stk.top(); stk.pop();</div><div class="line">                    s[sn].push_back(w[pre][vn]);</div><div class="line">                    pre = vn;</div><div class="line">                    belong[vn] = block;</div><div class="line">                    inStack[vn] = <span class="literal">false</span>;</div><div class="line">                &#125; <span class="keyword">while</span> (vn != v);</div><div class="line">                <span class="keyword">if</span> (s[sn].size() &gt; <span class="number">1</span>) s[sn].push_back(w[u][pre]);</div><div class="line">                <span class="keyword">else</span> s[sn--].clear();</div><div class="line">            &#125;</div><div class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (inStack[v]) &#123;</div><div class="line">            low[u] = min(low[u], dfn[v]);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</div><div class="line">    initGraph(n);</div><div class="line">    sn = <span class="number">0</span>; sumW = <span class="number">0</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) s[i].clear();</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Node</span> &#123;</span></div><div class="line">    <span class="keyword">int</span> val; <span class="keyword">int</span> p;</div><div class="line">    Node() &#123;&#125;</div><div class="line">    Node(<span class="keyword">int</span> a, <span class="keyword">int</span> b) &#123;</div><div class="line">        val = a; p = b;</div><div class="line">    &#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Heap</span> &#123;</span></div><div class="line">    Node tree[<span class="number">2000010</span>];</div><div class="line">    <span class="keyword">int</span> tn;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">()</span> </span>&#123;</div><div class="line">        tn = <span class="number">0</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">const</span> Node &amp;a)</span> </span>&#123;</div><div class="line">        tree[++tn] = a;</div><div class="line">        <span class="keyword">int</span> p = tn;</div><div class="line">        <span class="keyword">while</span> (p &gt; <span class="number">1</span> &amp;&amp; tree[p].val &gt; tree[p &gt;&gt; <span class="number">1</span>].val) &#123;</div><div class="line">            swap(tree[p &gt;&gt; <span class="number">1</span>], tree[p]);</div><div class="line">            p &gt;&gt;= <span class="number">1</span>;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="function">Node <span class="title">top</span><span class="params">()</span> </span>&#123;</div><div class="line">        <span class="keyword">return</span> tree[<span class="number">1</span>];</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">bool</span> <span class="title">empty</span><span class="params">()</span> </span>&#123;</div><div class="line">        <span class="keyword">return</span> tn == <span class="number">0</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">pop</span><span class="params">()</span> </span>&#123;</div><div class="line">        tree[<span class="number">1</span>] = tree[tn--];</div><div class="line">        <span class="keyword">int</span> p = <span class="number">1</span>;</div><div class="line">        <span class="keyword">while</span> (p &lt;= tn) &#123;</div><div class="line">            <span class="keyword">int</span> lch = p &lt;&lt; <span class="number">1</span>, rch = lch | <span class="number">1</span>;</div><div class="line">            <span class="keyword">if</span> (lch &lt;= tn &amp;&amp; rch &lt;= tn) &#123;</div><div class="line">                <span class="keyword">if</span> (tree[p].val &gt;= tree[lch].val &amp;&amp; tree[p].val &gt;= tree[rch].val) <span class="keyword">break</span>;</div><div class="line">                <span class="keyword">else</span> <span class="keyword">if</span> (tree[lch].val &gt;= tree[rch].val) &#123;</div><div class="line">                    swap(tree[p], tree[lch]);</div><div class="line">                    p = lch;</div><div class="line">                &#125; <span class="keyword">else</span> &#123;</div><div class="line">                    swap(tree[p], tree[rch]);</div><div class="line">                    p = rch;</div><div class="line">                &#125;</div><div class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (lch &lt;= tn) &#123;</div><div class="line">                <span class="keyword">if</span> (tree[p].val &gt;= tree[lch].val) <span class="keyword">break</span>;</div><div class="line">                <span class="keyword">else</span> &#123;</div><div class="line">                    swap(tree[p], tree[lch]);</div><div class="line">                    p = lch;</div><div class="line">                &#125;</div><div class="line">            &#125; <span class="keyword">else</span> &#123;</div><div class="line">                <span class="keyword">break</span>;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;q;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">merge</span><span class="params">(<span class="keyword">int</span> u, <span class="keyword">int</span> k)</span> </span>&#123;</div><div class="line">    <span class="keyword">if</span> (an &lt;= s[u].size()) &#123;</div><div class="line">        q.init();</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; an; i++) q.push(Node(a[i] + s[u][<span class="number">0</span>], <span class="number">0</span>));</div><div class="line">        an = <span class="number">0</span>;</div><div class="line">        <span class="keyword">int</span> sz = s[u].size();</div><div class="line">        <span class="keyword">while</span> (an &lt; k &amp;&amp; !q.empty()) &#123;</div><div class="line">            Node t = q.top(); q.pop();</div><div class="line">            a[an++] = t.val;</div><div class="line">            <span class="keyword">if</span> (t.p + <span class="number">1</span> &lt; sz) q.push(Node(t.val + s[u][t.p + <span class="number">1</span>] - s[u][t.p], t.p + <span class="number">1</span>));</div><div class="line">        &#125;</div><div class="line">    &#125; <span class="keyword">else</span> &#123;</div><div class="line">        bn = an;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; an; i++) b[i] = a[i];</div><div class="line">        q.init();</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; s[u].size(); i++) q.push(Node(a[<span class="number">0</span>] + s[u][i], <span class="number">0</span>));</div><div class="line">        an = <span class="number">0</span>;</div><div class="line">        <span class="keyword">int</span> sz = s[u].size();</div><div class="line">        <span class="keyword">while</span> (an &lt; k &amp;&amp; !q.empty()) &#123;</div><div class="line">            Node t = q.top(); q.pop();</div><div class="line">            a[an++] = t.val;</div><div class="line">            <span class="keyword">if</span> (t.p + <span class="number">1</span> &lt; bn) q.push(Node(t.val + b[t.p + <span class="number">1</span>] - b[t.p], t.p + <span class="number">1</span>));</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">(<span class="keyword">int</span> n, <span class="keyword">int</span> m, <span class="keyword">int</span> kk)</span> </span>&#123;</div><div class="line">    init(n);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</div><div class="line">        <span class="keyword">int</span> x, y; <span class="keyword">int</span> z;</div><div class="line">        <span class="built_in">scanf</span>(<span class="string">"%d%d%d"</span>, &amp;x, &amp;y, &amp;z);</div><div class="line">        addEdge(x, y, z);</div><div class="line">        sumW += z;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">int</span> k; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;k);</div><div class="line">    tarjan(<span class="number">1</span>, <span class="number">0</span>);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= sn; i++) sort(s[i].begin(), s[i].end(), greater&lt;<span class="keyword">int</span>&gt;());</div><div class="line">    an = <span class="number">0</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; k &amp;&amp; i &lt; s[<span class="number">1</span>].size(); i++) a[an++] = s[<span class="number">1</span>][i];</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">2</span>; i &lt;= sn; i++) merge(i, k);</div><div class="line">    <span class="keyword">if</span> (sn == <span class="number">0</span>) a[an++] = <span class="number">0</span>;</div><div class="line">    <span class="keyword">int</span> ans = <span class="number">0</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; an; i++) ans += (i + <span class="number">1</span>) * (sumW - a[i]);</div><div class="line">    <span class="built_in">printf</span>(<span class="string">"Case #%d: %u\n"</span>, kk, ans);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> n, m;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> kk = <span class="number">1</span>; <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;n, &amp;m) != EOF; kk++) solve(n, m, kk);</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/hdu6076/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hdu6076/" itemprop="url">hdu 6076 Security Check (动态规划)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-08-07T00:00:00+08:00">
                2017-08-07
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/hdu6076/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/hdu6076/" class="cy_cmt_count" data-xid="hdu6076/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>设$dp<em>{i,j}$表示仅考虑$a</em>{1..i}$和$b_{1..j}$时，最少需要多少时间。</p>
<p>则<br>$$<br>dp<em>{i,j} =<br>\begin{cases}<br>dp</em>{i-1,j-1}+1 &amp; a<em>{i} = b</em>{j}\<br>\min {(dp<em>{i-1,j}, dp</em>{i,j-1})+1} &amp; a<em>{i} \neq b</em>{j}<br>\end{cases}<br>$$</p>
<p>可以发现$a<em>{i} \neq b</em>{j}$部分的式子只有$O(nk)$个，可以暴力DP。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">60010</span>;</div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> K = <span class="number">15</span>;</div><div class="line"><span class="keyword">int</span> a[N], b[N], dp[N][K &lt;&lt; <span class="number">1</span>];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">DP</span><span class="params">(<span class="keyword">int</span> n, <span class="keyword">int</span> m, <span class="keyword">int</span> k)</span> </span>&#123;</div><div class="line">    <span class="keyword">if</span> (n == <span class="number">0</span> || m == <span class="number">0</span>) <span class="keyword">return</span> n + m;</div><div class="line">    <span class="keyword">int</span> ans = <span class="number">0</span>;</div><div class="line">    <span class="keyword">if</span> (<span class="built_in">abs</span>(a[n] - b[m]) &lt;= k) &#123;</div><div class="line">        <span class="keyword">int</span> t = a[n] - b[m] + k;</div><div class="line">        <span class="keyword">if</span> (dp[n][t] != <span class="number">0</span>) <span class="keyword">return</span> dp[n][t];</div><div class="line">        <span class="keyword">return</span> dp[n][t] = min(DP(n - <span class="number">1</span>, m, k), DP(n, m - <span class="number">1</span>, k)) + <span class="number">1</span>;</div><div class="line">    &#125; <span class="keyword">else</span> &#123;</div><div class="line">        <span class="keyword">return</span> DP(n - <span class="number">1</span>, m - <span class="number">1</span>, k) + <span class="number">1</span>;</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="built_in">memset</span>(dp, <span class="number">0</span>, <span class="keyword">sizeof</span> dp);</div><div class="line">    <span class="keyword">int</span> n, k; <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;n, &amp;k);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;a[i]);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;b[i]);</div><div class="line">    <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, DP(n, n, k));</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> T; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;T);</div><div class="line">    <span class="keyword">while</span> (T--) solve();</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/hdu6083/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hdu6083/" itemprop="url">hdu 6083 度度熊的午饭时光 (动态规划)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-08-07T00:00:00+08:00">
                2017-08-07
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/hdu6083/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/hdu6083/" class="cy_cmt_count" data-xid="hdu6083/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>很裸的01背包问题。但是题目中有一个要求是序号和最小。对于这样的限制我们可以再增加一个sum数组，记录当前dp情况下的序号和。然后dp过程中再增加$dp<em>{k,j-cost</em>{i}} + score<em>{i} == dp</em>{i,j} \wedge sum<em>{k,j-cost</em>{i}} + i &lt; sum_{i,j}$的情况就可以了。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> B = <span class="number">1010</span>;</div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">110</span>;</div><div class="line"><span class="keyword">int</span> dp[N][B], fat[N][B][<span class="number">2</span>], sum[N][B], score[N], cost[N]; </div><div class="line"><span class="built_in">stack</span>&lt;<span class="keyword">int</span>&gt; stk;</div><div class="line"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; ans1, ans2;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">(<span class="keyword">int</span> kk)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> b; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;b);</div><div class="line">    <span class="built_in">memset</span>(dp, <span class="number">0</span>, <span class="keyword">sizeof</span> dp);</div><div class="line">    <span class="built_in">memset</span>(sum, <span class="number">0x3f</span>, <span class="keyword">sizeof</span> sum);</div><div class="line">    <span class="built_in">memset</span>(fat, <span class="number">0</span>, <span class="keyword">sizeof</span> fat);</div><div class="line">    ans1.clear(); ans2.clear();</div><div class="line">    <span class="keyword">int</span> n; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;n);</div><div class="line">    sum[<span class="number">0</span>][<span class="number">0</span>] = <span class="number">0</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;score[i], &amp;cost[i]);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = cost[i]; j &lt;= b; j++) &#123;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> k = <span class="number">0</span>; k &lt; i; k++) &#123;</div><div class="line">                <span class="keyword">if</span> (dp[k][j-cost[i]] + score[i] &gt; dp[i][j]) &#123;</div><div class="line">                    dp[i][j] = dp[k][j-cost[i]] + score[i];</div><div class="line">                    sum[i][j] = sum[k][j-cost[i]] + i;</div><div class="line">                    fat[i][j][<span class="number">0</span>] = k;</div><div class="line">                    fat[i][j][<span class="number">1</span>] = j - cost[i];</div><div class="line">                &#125; <span class="keyword">else</span> <span class="keyword">if</span> (dp[k][j-cost[i]] + score[i] == dp[i][j]) &#123;</div><div class="line">                    <span class="keyword">if</span> (sum[k][j-cost[i]] + i &lt; sum[i][j]) &#123;</div><div class="line">                        sum[i][j] = sum[k][j-cost[i]] + i;</div><div class="line">                        fat[i][j][<span class="number">0</span>] = k;</div><div class="line">                        fat[i][j][<span class="number">1</span>] = j - cost[i];</div><div class="line">                    &#125;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">int</span> mxdp = <span class="number">0</span>, mnsum = <span class="number">0x3f3f3f3f</span>, ti, tj;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = cost[i]; j &lt;= b; j++) &#123;</div><div class="line">            <span class="keyword">if</span> (dp[i][j] &gt; mxdp || (dp[i][j] == mxdp &amp;&amp; sum[i][j] &lt; mnsum)) &#123;</div><div class="line">                mxdp = dp[i][j];</div><div class="line">                mnsum = sum[i][j];</div><div class="line">                ti = i;</div><div class="line">                tj = j;</div><div class="line">            &#125; </div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">bool</span> flag = <span class="literal">true</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = cost[i]; j &lt;= b; j++) &#123;</div><div class="line">            <span class="keyword">if</span> (dp[i][j] == mxdp &amp;&amp; sum[i][j] == mnsum) &#123;</div><div class="line">                <span class="keyword">while</span> (!stk.empty()) stk.pop();</div><div class="line">                <span class="keyword">int</span> ti = i, tj = j;</div><div class="line">                <span class="keyword">while</span> (ti != <span class="number">0</span>) &#123;</div><div class="line">                    stk.push(ti);</div><div class="line">                    <span class="keyword">int</span> pi = ti, pj = tj;</div><div class="line">                    ti = fat[pi][pj][<span class="number">0</span>];</div><div class="line">                    tj = fat[pi][pj][<span class="number">1</span>];</div><div class="line">                &#125;</div><div class="line">                ans2.clear();</div><div class="line">                <span class="keyword">while</span> (!stk.empty()) &#123;</div><div class="line">                    ans2.push_back(stk.top()); stk.pop();</div><div class="line">                &#125;</div><div class="line">                <span class="keyword">if</span> (flag) &#123;</div><div class="line">                    ans1 = ans2;</div><div class="line">                    flag = <span class="literal">false</span>;</div><div class="line">                &#125; <span class="keyword">else</span> &#123;</div><div class="line">                    <span class="keyword">int</span> cmp = <span class="number">0</span>;</div><div class="line">                    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; ans1.size() &amp;&amp; i &lt; ans2.size(); i++) &#123;</div><div class="line">                        cmp = ans1[i] - ans2[i];</div><div class="line">                        <span class="keyword">if</span> (cmp != <span class="number">0</span>) <span class="keyword">break</span>;</div><div class="line">                    &#125;</div><div class="line">                    <span class="keyword">if</span> (cmp &gt; <span class="number">0</span>) ans1 = ans2;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">int</span> mxcost = <span class="number">0</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; ans1.size(); i++) mxcost += cost[ans1[i]];</div><div class="line">    <span class="built_in">printf</span>(<span class="string">"Case #%d:\n"</span>, kk);</div><div class="line">    <span class="keyword">if</span> (mxdp == <span class="number">0</span>) &#123;</div><div class="line">        ans1.clear();</div><div class="line">        mxcost = <span class="number">0</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="built_in">printf</span>(<span class="string">"%d %d\n"</span>, mxdp, mxcost);</div><div class="line">    <span class="keyword">if</span> (!ans1.empty()) &#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; ans1.size(); i++) &#123;</div><div class="line">            <span class="built_in">printf</span>(<span class="string">"%d"</span>, ans1[i]);</div><div class="line">            <span class="keyword">if</span> (i + <span class="number">1</span> == ans1.size()) <span class="built_in">printf</span>(<span class="string">"\n"</span>);</div><div class="line">            <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">" "</span>);</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> T; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;T);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> kk = <span class="number">1</span>; kk &lt;= T; kk++) solve(kk);</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/hdu6078/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hdu6078/" itemprop="url">hdu 6078 Wavel Sequence (动态规划)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-08-06T00:00:00+08:00">
                2017-08-06
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/hdu6078/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/hdu6078/" class="cy_cmt_count" data-xid="hdu6078/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>我们假设固定$a<em>{i}$，枚举$b</em>{j}$，设$sum<em>{j,0…1}$表示$k \in [1,i)$且$a</em>{k}=b<em>{j}$的情况的相应波浪总数，那么对于当前$a</em>{i}$来说，假设已经枚举到$b<em>{j}$，设$cnt</em>{s}$表示$\sum<em>{k \in [1, j),a</em>{i} &lt; b<em>{k}} {sum</em>{k,s}}$和$\sum<em>{k \in [1, j),a</em>{i} &gt; b<em>{k}} {sum</em>{k,s}}$，那么对于$a<em>{i}=b</em>{j}$的情况，答案就会增加$cnt<em>{0}$和$cnt</em>{1}+1$。同时根据$a<em>{i}$和$b</em>{j}$的大小关系，维护$sum$数组就行了。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">2010</span>;</div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> MOD = <span class="number">998244353</span>;</div><div class="line"><span class="keyword">int</span> a[N], b[N], sum[N][<span class="number">2</span>], cnt[<span class="number">2</span>];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">(<span class="keyword">int</span> n, <span class="keyword">int</span> m)</span> </span>&#123;</div><div class="line">    <span class="built_in">memset</span>(sum, <span class="number">0</span>, <span class="keyword">sizeof</span> sum);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">int</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y)</span> </span>&#123;</div><div class="line">    <span class="keyword">return</span> x + y &gt;= MOD ? x + y - MOD : x + y;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> n, m; <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;n, &amp;m);</div><div class="line">    init(n, m);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;a[i]);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= m; i++) <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;b[i]);</div><div class="line"></div><div class="line">    <span class="keyword">int</span> ans = <span class="number">0</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        cnt[<span class="number">0</span>] = cnt[<span class="number">1</span>] = <span class="number">0</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt;= m; j++) &#123;</div><div class="line">            <span class="keyword">if</span> (a[i] == b[j]) &#123;</div><div class="line">                ans = add(ans, add(add(cnt[<span class="number">1</span>], <span class="number">1</span>), cnt[<span class="number">0</span>]));</div><div class="line">                sum[j][<span class="number">0</span>] = add(sum[j][<span class="number">0</span>], add(cnt[<span class="number">1</span>], <span class="number">1</span>));</div><div class="line">                sum[j][<span class="number">1</span>] = add(sum[j][<span class="number">1</span>], cnt[<span class="number">0</span>]);</div><div class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (a[i] &lt; b[j]) &#123;</div><div class="line">                cnt[<span class="number">1</span>] = add(cnt[<span class="number">1</span>], sum[j][<span class="number">1</span>]);</div><div class="line">            &#125; <span class="keyword">else</span> &#123;</div><div class="line">                cnt[<span class="number">0</span>] = add(cnt[<span class="number">0</span>], sum[j][<span class="number">0</span>]);</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, ans);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> T; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;T);</div><div class="line">    <span class="keyword">while</span> (T--) solve();</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/hdu6074/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hdu6074/" itemprop="url">hdu 6074 Phone Call (LCA+并查集)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-08-06T00:00:00+08:00">
                2017-08-06
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/hdu6074/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/hdu6074/" class="cy_cmt_count" data-xid="hdu6074/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>将所有线路按代价从小到大排序，对于每条线路$(a, b, c, d)$，首先把$a$到$b$路径上的点都合并到LCA，再把$c$到$d$路径上的点都合并到LCA，最后再把两个LCA合并。所谓的合并其实就是合并两个东西，一个是这条电话线路上的所有点的个数，另一个是这条电话线路上的点全部接通所需要的花费。<br>在$a,b,c,d$到LCA的合并过程中，我们可以做出一些优化，例如$a$点下一步只需要跳到下一个与$a$不属于同一连通块的位置，也就是说之前已经合并过的连通块部分可以只访问一次就行。举个例子，$5 \to 4 \to 3 \to 2 \to 1$，假设$4,3$之前已经属于同一块了，$2,1$也属于同一连通块，那我们可以只访问$5 \to 4 \to 2$即可。这部分可以再用一个并查集来维护。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">PhoneLine</span> &#123;</span></div><div class="line">    <span class="keyword">int</span> a, b, c, d; LL w;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">read</span><span class="params">()</span> </span>&#123;</div><div class="line">        <span class="built_in">scanf</span>(<span class="string">"%d%d%d%d%lld"</span>, &amp;a, &amp;b, &amp;c, &amp;d, &amp;w);</div><div class="line">    &#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">bool</span> <span class="title">cmpPhoneLine</span><span class="params">(<span class="keyword">const</span> PhoneLine &amp;a, <span class="keyword">const</span> PhoneLine &amp;b)</span> </span>&#123;</div><div class="line">    <span class="keyword">return</span> a.w &lt; b.w;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">100010</span>;</div><div class="line"><span class="built_in">vector</span>&lt;<span class="keyword">int</span>&gt; g[N];</div><div class="line">PhoneLine phoneLine[N];</div><div class="line"><span class="keyword">int</span> fatNode[N], dep[N];</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">ST</span> &#123;</span></div><div class="line">    <span class="keyword">enum</span> &#123;ST_SIZE = <span class="number">20</span>&#125;;</div><div class="line">    <span class="keyword">int</span> logTwo[N &lt;&lt; <span class="number">1</span>], st[N &lt;&lt; <span class="number">1</span>][ST_SIZE];</div><div class="line"></div><div class="line">    ST() &#123;</div><div class="line">        logTwo[<span class="number">0</span>] = <span class="number">-1</span>;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; (N &lt;&lt; <span class="number">1</span>); i++) &#123;</div><div class="line">            logTwo[i] = ((i &amp; (i - <span class="number">1</span>)) == <span class="number">0</span>) ? logTwo[i<span class="number">-1</span>] + <span class="number">1</span> : logTwo[i<span class="number">-1</span>];</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">(<span class="keyword">int</span> *a, <span class="keyword">int</span> n)</span> </span>&#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) st[i][<span class="number">0</span>] = a[i];</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j &lt; ST_SIZE; j++)</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i + (<span class="number">1</span> &lt;&lt; j) &lt;= n + <span class="number">1</span>; i++) </div><div class="line">            st[i][j] = min(st[i][j<span class="number">-1</span>], st[i + (<span class="number">1</span> &lt;&lt; (j<span class="number">-1</span>))][j<span class="number">-1</span>]);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">query</span><span class="params">(<span class="keyword">int</span> l, <span class="keyword">int</span> r)</span> </span>&#123;</div><div class="line">        <span class="keyword">int</span> k = logTwo[r-l+<span class="number">1</span>];</div><div class="line">        <span class="keyword">return</span> min(st[l][k], st[r+<span class="number">1</span>-(<span class="number">1</span>&lt;&lt;k)][k]);</div><div class="line">    &#125;</div><div class="line">&#125;st;</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">LCA</span> &#123;</span></div><div class="line">    <span class="keyword">int</span> p, m;</div><div class="line">    <span class="keyword">int</span> mp[N &lt;&lt; <span class="number">1</span>], val[N &lt;&lt; <span class="number">1</span>], first[N];</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">()</span> </span>&#123;</div><div class="line">        p = m = <span class="number">0</span>;</div><div class="line">        dfs(<span class="number">1</span>, <span class="number">0</span>, <span class="number">1</span>);</div><div class="line">        st.init(val, m);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> u, <span class="keyword">int</span> f, <span class="keyword">int</span> depth)</span> </span>&#123;</div><div class="line">        fatNode[u] = f;</div><div class="line">        dep[u] = depth;</div><div class="line">        mp[++p] = u;</div><div class="line">        val[++m] = p;</div><div class="line">        first[u] = m;</div><div class="line">        <span class="keyword">int</span> t = p;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; g[u].size(); i++) &#123;</div><div class="line">            <span class="keyword">int</span> v = g[u][i];</div><div class="line">            <span class="keyword">if</span> (v == f) <span class="keyword">continue</span>;</div><div class="line">            dfs(v, u, depth + <span class="number">1</span>);</div><div class="line">            val[++m] = t;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">query</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b)</span> </span>&#123;</div><div class="line">        <span class="keyword">if</span> (first[a] &gt; first[b]) swap(a, b);</div><div class="line">        <span class="keyword">return</span> mp[st.query(first[a], first[b])];</div><div class="line">    &#125;</div><div class="line">&#125;lca;</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">UnionFind</span> &#123;</span></div><div class="line">    <span class="keyword">int</span> fat[N], cnt[N], same[N];</div><div class="line">    LL cost[N];</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">            fat[i] = same[i] = i; </div><div class="line">            cnt[i] = <span class="number">1</span>; cost[i] = <span class="number">0</span>;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">getFather</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</div><div class="line">        <span class="keyword">return</span> x == fat[x] ? x : fat[x] = getFather(fat[x]);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">int</span> <span class="title">getSame</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</div><div class="line">        <span class="keyword">return</span> x == same[x] ? x : same[x] = getSame(same[x]);</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">jump</span><span class="params">(<span class="keyword">int</span> u, <span class="keyword">int</span> v, LL w)</span> </span>&#123;</div><div class="line">        <span class="keyword">while</span> (<span class="literal">true</span>) &#123;</div><div class="line">            u = getSame(u);</div><div class="line">            <span class="keyword">if</span> (dep[u] &lt;= dep[v]) <span class="keyword">break</span>;</div><div class="line">            merge(u, fatNode[u], w);</div><div class="line">            same[u] = fatNode[u];</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">merge</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y, LL w)</span> </span>&#123;</div><div class="line">        <span class="keyword">int</span> fx = getFather(x);</div><div class="line">        <span class="keyword">int</span> fy = getFather(y);</div><div class="line">        <span class="keyword">if</span> (fx == fy) <span class="keyword">return</span>;</div><div class="line">        cnt[fx] += cnt[fy];</div><div class="line">        cost[fx] += cost[fy] + w;</div><div class="line">        fat[fy] = fx;</div><div class="line">        <span class="comment">//printf("merge: x=%d, y=%d, fx=%d, fy=%d\n", x, y, fx, fy);</span></div><div class="line">        <span class="comment">//printf("cnt[%d]=%d, cost[%d]=%lld\n", fx, cnt[fx], fx, cost[fx]);</span></div><div class="line">    &#125;</div><div class="line"></div><div class="line">    <span class="function"><span class="keyword">void</span> <span class="title">output</span><span class="params">()</span> </span>&#123;</div><div class="line">        <span class="built_in">printf</span>(<span class="string">"%d %lld\n"</span>, cnt[getFather(<span class="number">1</span>)], cost[getFather(<span class="number">1</span>)]);</div><div class="line">    &#125;</div><div class="line">&#125;unionFind;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</div><div class="line">    dep[<span class="number">0</span>] = <span class="number">0</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) g[i].clear();</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">input</span><span class="params">(<span class="keyword">int</span> n, <span class="keyword">int</span> m)</span> </span>&#123;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt; n; i++) &#123;</div><div class="line">        <span class="keyword">int</span> u, v; <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;u, &amp;v);</div><div class="line">        g[u].push_back(v);</div><div class="line">        g[v].push_back(u);</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; m; i++) &#123;</div><div class="line">        phoneLine[i].read();</div><div class="line">    &#125;</div><div class="line">    sort(phoneLine, phoneLine + m, cmpPhoneLine);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">handle</span><span class="params">(<span class="keyword">int</span> p)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> a = phoneLine[p].a, b = phoneLine[p].b;</div><div class="line">    <span class="keyword">int</span> c = phoneLine[p].c, d = phoneLine[p].d;</div><div class="line">    LL w = phoneLine[p].w;</div><div class="line">    <span class="keyword">int</span> lcaAB = lca.query(a, b), lcaCD = lca.query(c, d);</div><div class="line">    unionFind.jump(a, lcaAB, w); unionFind.jump(b, lcaAB, w);</div><div class="line">    unionFind.jump(c, lcaCD, w); unionFind.jump(d, lcaCD, w);</div><div class="line">    unionFind.merge(lcaAB, lcaCD, w);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> n, m; <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>, &amp;n, &amp;m);</div><div class="line">    init(n);</div><div class="line">    input(n, m);</div><div class="line">    lca.init();</div><div class="line">    unionFind.init(n);</div><div class="line">    </div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; m; i++) handle(i);</div><div class="line"></div><div class="line">    unionFind.output();</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> T; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;T);</div><div class="line">    <span class="keyword">while</span> (T--) solve();</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/hdu6073/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hdu6073/" itemprop="url">hdu 6073 Matching In Multiplication (拓扑排序+DFS)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-08-05T00:00:00+08:00">
                2017-08-05
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/hdu6073/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/hdu6073/" class="cy_cmt_count" data-xid="hdu6073/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>如果一个点的度数为$1$，那么这个点的匹配方案肯定是固定的，于是我们可以删掉这一对点。通过拓扑我们可以不断去掉所有度数为$1$的点对。那么剩下的图中左右各有$m$个点，右侧每个点度数都不小于$2$，且左边每个点度数都是$2$，由此可以推出右侧每个点的度数均为$2$。不难想到剩下的图是由若干个环组成，且每个环都只有两种取法。那么最终答案为$ans = shareProduct * \prod {(res<em>{i,0}+res</em>{i,1})}$。其中$shareProduct$表示刚开始我们删掉的固定边的乘积，$res<em>{i,0},res</em>{i,1}$分别表示第$i$个环的两种取法的权值乘积。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</div><div class="line"></div><div class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Edge</span> &#123;</span></div><div class="line">    <span class="keyword">int</span> v; LL w;</div><div class="line">    Edge(<span class="keyword">int</span> a = <span class="number">0</span>, LL b = <span class="number">0</span>) &#123;</div><div class="line">        v = a; w = b;</div><div class="line">    &#125;</div><div class="line">&#125;;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">300010</span>;</div><div class="line"><span class="keyword">const</span> LL MOD = <span class="number">998244353</span>;</div><div class="line"><span class="keyword">int</span> degRight[N];</div><div class="line"><span class="built_in">vector</span>&lt;Edge&gt; g[N][<span class="number">2</span>];</div><div class="line"><span class="keyword">bool</span> exist[N][<span class="number">2</span>], vis[<span class="number">2</span>][N][<span class="number">2</span>];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        g[i][<span class="number">0</span>].clear(); g[i][<span class="number">1</span>].clear();</div><div class="line">    &#125;</div><div class="line">    <span class="built_in">memset</span>(exist, <span class="literal">true</span>, <span class="keyword">sizeof</span> exist);</div><div class="line">    <span class="built_in">memset</span>(degRight, <span class="number">0</span>, <span class="keyword">sizeof</span> degRight);</div><div class="line">    <span class="built_in">memset</span>(vis, <span class="literal">false</span>, <span class="keyword">sizeof</span> vis);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function">LL <span class="title">deleteDegreeOne</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</div><div class="line">    LL shareProduct = <span class="number">1</span>;</div><div class="line">    <span class="built_in">queue</span>&lt;<span class="keyword">int</span>&gt; q;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        <span class="keyword">if</span> (degRight[i] == <span class="number">1</span>) &#123;</div><div class="line">            q.push(i);</div><div class="line">            exist[i][<span class="number">1</span>] = <span class="literal">false</span>;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">while</span> (!q.empty()) &#123;</div><div class="line">        <span class="keyword">int</span> x = q.front(); q.pop();</div><div class="line">        <span class="keyword">int</span> u;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; g[x][<span class="number">1</span>].size(); i++) &#123;</div><div class="line">            u = g[x][<span class="number">1</span>][i].v;</div><div class="line">            <span class="keyword">if</span> (exist[u][<span class="number">0</span>]) &#123;</div><div class="line">                exist[u][<span class="number">0</span>] = <span class="literal">false</span>;</div><div class="line">                shareProduct = shareProduct * g[x][<span class="number">1</span>][i].w % MOD;</div><div class="line">                <span class="keyword">break</span>;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; g[u][<span class="number">0</span>].size(); i++) &#123;</div><div class="line">            <span class="keyword">int</span> v = g[u][<span class="number">0</span>][i].v;</div><div class="line">            <span class="keyword">if</span> (exist[v][<span class="number">1</span>]) &#123;</div><div class="line">                degRight[v]--;</div><div class="line">                <span class="keyword">if</span> (degRight[v] == <span class="number">1</span>) &#123;</div><div class="line">                    exist[v][<span class="number">1</span>] = <span class="literal">false</span>;</div><div class="line">                    q.push(v);</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> shareProduct;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function">LL <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> cur, <span class="keyword">int</span> u, <span class="keyword">int</span> p)</span> </span>&#123;</div><div class="line">    vis[cur][u][p] = <span class="literal">true</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; g[u][p].size(); i++) &#123;</div><div class="line">        <span class="keyword">int</span> v = g[u][p][i].v;</div><div class="line">        <span class="keyword">if</span> (!vis[cur][v][p^<span class="number">1</span>] &amp;&amp; exist[v][p^<span class="number">1</span>]) &#123;</div><div class="line">            <span class="keyword">return</span> p == <span class="number">0</span> ? dfs(cur, v, p ^ <span class="number">1</span>) : g[u][p][i].w * dfs(cur, v, p ^ <span class="number">1</span>) % MOD;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> <span class="number">1</span>;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="comment">//printf("============\n");</span></div><div class="line">    <span class="keyword">int</span> n; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;n);</div><div class="line">    init(n);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; <span class="number">2</span>; j++) &#123;</div><div class="line">            <span class="keyword">int</span> v; LL w; <span class="built_in">scanf</span>(<span class="string">"%d%lld"</span>, &amp;v, &amp;w);</div><div class="line">            degRight[v]++;</div><div class="line">            g[i][<span class="number">0</span>].push_back(Edge(v, w % MOD));</div><div class="line">            g[v][<span class="number">1</span>].push_back(Edge(i, w % MOD));</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    LL shareProduct = deleteDegreeOne(n);</div><div class="line">    LL ans = <span class="number">1</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        <span class="keyword">if</span> (degRight[i] &gt; <span class="number">1</span> &amp;&amp; !vis[<span class="number">0</span>][i][<span class="number">1</span>] &amp;&amp; !vis[<span class="number">1</span>][i][<span class="number">1</span>]) &#123;</div><div class="line">            LL res = <span class="number">0</span>; <span class="keyword">int</span> cur = <span class="number">0</span>;</div><div class="line">            <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; g[i][<span class="number">1</span>].size(); j++) &#123;</div><div class="line">                <span class="keyword">int</span> v = g[i][<span class="number">1</span>][j].v; LL w = g[i][<span class="number">1</span>][j].w;</div><div class="line">                <span class="keyword">if</span> (exist[v][<span class="number">0</span>]) &#123;</div><div class="line">                    vis[cur][i][<span class="number">1</span>] = <span class="literal">true</span>;</div><div class="line">                    res += w * dfs(cur, v, <span class="number">0</span>) % MOD; res %= MOD;</div><div class="line">                    cur++;</div><div class="line">                &#125;</div><div class="line">            &#125;</div><div class="line">            ans *= res; ans %= MOD;</div><div class="line">        &#125;</div><div class="line">    &#125;</div><div class="line">    <span class="comment">//printf("%lld %lld %lld\n", ans * shareProduct % MOD, ans, shareProduct);</span></div><div class="line">    <span class="built_in">printf</span>(<span class="string">"%lld\n"</span>, ans * shareProduct % MOD);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> T; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;T);</div><div class="line">    <span class="keyword">while</span> (T--) solve();</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
      

  

  
  
  

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="http://localhost/hdu6059/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="cayun">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/img/head.png">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="cayun's blog">
    </span>

    
      <header class="post-header">

        
        
          <h2 class="post-title" itemprop="name headline">
                
                <a class="post-title-link" href="/hdu6059/" itemprop="url">hdu 6059 Kanade's trio (字典树)</a></h2>
        

        <div class="post-meta">
          <span class="post-time">
            
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              
                <span class="post-meta-item-text">发表于</span>
              
              <time title="创建于" itemprop="dateCreated datePublished" datetime="2017-08-05T00:00:00+08:00">
                2017-08-05
              </time>
            

            

            
          </span>

          

          
            
              <span class="post-comments-count">
              <span class="post-meta-divider">|</span>
              <span class="post-meta-item-icon">
                <i class="fa fa-comment-o"></i>
              </span>
              
                <a href="/hdu6059/#SOHUCS" itemprop="discussionUrl">
                  <span id="url::http://localhost/hdu6059/" class="cy_cmt_count" data-xid="hdu6059/" itemprop="commentsCount" ></span>
                </a>
              
            
          

          
          

          

          

          

        </div>
      </header>
    

    
    
    
    <div class="post-body han-init-context" itemprop="articleBody">

      
      

      
        
          
            <h1 id="解法"><a href="#解法" class="headerlink" title="解法"></a>解法</h1><p>考虑$A<em>{i}$和$A</em>{k}$不同位中的最高位，根据这一位可以知道$A<em>{j}$这一位的值。于是我们枚举$A</em>{k}$，将$A<em>{1}…A</em>{k-1}$都插入字典树中，顺便记录从 $A<em>{1}…A</em>{k-1}$中第$x$位为$0,1$的数量，然后就可以直接计算出来了。但是这样可能会计算进$j &lt;= i$的情况，于是我们需要对字典树的每个节点记录一下重复的部分，然后减去即可。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="code"><pre><div class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;bits/stdc++.h&gt;</span></span></div><div class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</div><div class="line"></div><div class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> LL;</div><div class="line"></div><div class="line"><span class="keyword">const</span> <span class="keyword">int</span> N = <span class="number">500010</span>;</div><div class="line"><span class="keyword">int</span> a[N], tree[N * <span class="number">30</span>][<span class="number">2</span>], tn;</div><div class="line">LL val[N * <span class="number">30</span>][<span class="number">2</span>], cnt[N * <span class="number">30</span>][<span class="number">2</span>], num[<span class="number">35</span>][<span class="number">2</span>];</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">(<span class="keyword">int</span> n)</span> </span>&#123;</div><div class="line">    tn = <span class="number">0</span>;</div><div class="line">    <span class="built_in">memset</span>(num, <span class="number">0</span>, <span class="keyword">sizeof</span> num);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt;= n * <span class="number">30</span>; i++)</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; <span class="number">2</span>; j++) </div><div class="line">        tree[i][j] = val[i][j] = cnt[i][j] = <span class="number">0</span>;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">insertTrie</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> p = <span class="number">0</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">29</span>; i &gt;= <span class="number">0</span>; i--) &#123;</div><div class="line">        <span class="keyword">int</span> y = (x &gt;&gt; i) &amp; <span class="number">1</span>;</div><div class="line">        num[i][y]++;</div><div class="line">        val[p][y]++;</div><div class="line">        cnt[p][y] += num[i][y];</div><div class="line">        <span class="keyword">if</span> (tree[p][y] == <span class="number">0</span>) tree[p][y] = ++tn;</div><div class="line">        p = tree[p][y];</div><div class="line">    &#125;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function">LL <span class="title">getAns</span><span class="params">(<span class="keyword">int</span> x)</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> p = <span class="number">0</span>; LL res = <span class="number">0</span>;</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">29</span>; i &gt;= <span class="number">0</span>; i--) &#123;</div><div class="line">        <span class="keyword">int</span> y = (x &gt;&gt; i) &amp; <span class="number">1</span>;</div><div class="line">        res += num[i][y^<span class="number">1</span>] * val[p][y^<span class="number">1</span>] - cnt[p][y^<span class="number">1</span>];</div><div class="line">        p = tree[p][y]; <span class="keyword">if</span> (p == <span class="number">0</span>) <span class="keyword">break</span>;</div><div class="line">    &#125;</div><div class="line">    <span class="keyword">return</span> res;</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span> </span>&#123;</div><div class="line">    LL ans = <span class="number">0</span>;</div><div class="line">    <span class="keyword">int</span> n; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;n);</div><div class="line">    init(n);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;a[i]);</div><div class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i &lt;= n; i++) &#123;</div><div class="line">        ans += getAns(a[i]);</div><div class="line">        insertTrie(a[i]);</div><div class="line">    &#125;</div><div class="line">    <span class="built_in">printf</span>(<span class="string">"%lld\n"</span>, ans);</div><div class="line">&#125;</div><div class="line"></div><div class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</div><div class="line">    <span class="keyword">int</span> T; <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &amp;T);</div><div class="line">    <span class="keyword">while</span> (T--) solve();</div><div class="line">    <span class="keyword">return</span> <span class="number">0</span>;</div><div class="line">&#125;</div></pre></td></tr></table></figure>
          
        
      
    </div>
    
    
    

    

    

    

    <footer class="post-footer">
      

      

      

      
      
        <div class="post-eof"></div>
      
    </footer>
  </div>
  
  
  
  </article>


    
  </section>

  
  <nav class="pagination">
    <a class="extend prev" rel="prev" href="/"><i class="fa fa-angle-left"></i></a><a class="page-number" href="/">1</a><span class="page-number current">2</span><a class="page-number" href="/page/3/">3</a><span class="space">&hellip;</span><a class="page-number" href="/page/11/">11</a><a class="extend next" rel="next" href="/page/3/"><i class="fa fa-angle-right"></i></a>
  </nav>



          </div>
          


          

        </div>
        
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    
    <div class="sidebar-inner">

      

      

      <section class="site-overview-wrap sidebar-panel sidebar-panel-active">
        <div class="site-overview">
          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
            
              <img class="site-author-image" itemprop="image"
                src="/img/head.png"
                alt="cayun" />
            
              <p class="site-author-name" itemprop="name">cayun</p>
              <p class="site-description motion-element" itemprop="description"></p>
          </div>

          <nav class="site-state motion-element">

            
              <div class="site-state-item site-state-posts">
              
                <a href="/archives/">
              
                  <span class="site-state-item-count">102</span>
                  <span class="site-state-item-name">日志</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-categories">
                <a href="/categories/index.html">
                  <span class="site-state-item-count">3</span>
                  <span class="site-state-item-name">分类</span>
                </a>
              </div>
            

            
              
              
              <div class="site-state-item site-state-tags">
                <a href="/tags/index.html">
                  <span class="site-state-item-count">79</span>
                  <span class="site-state-item-name">标签</span>
                </a>
              </div>
            

          </nav>

          

          <div class="links-of-author motion-element">
            
              
                <span class="links-of-author-item">
                  <a href="https://github.com/comeacrossyun" target="_blank" title="GitHub">
                    
                      <i class="fa fa-fw fa-github"></i>GitHub</a>
                </span>
              
                <span class="links-of-author-item">
                  <a href="mailto:comeacrossyun@gmail.com" target="_blank" title="E-Mail">
                    
                      <i class="fa fa-fw fa-envelope"></i>E-Mail</a>
                </span>
              
            
          </div>

          
          

          
          

          

        </div>
      </section>

      

      
        <div class="back-to-top">
          <i class="fa fa-arrow-up"></i>
          
            <span id="scrollpercent"><span>0</span>%</span>
          
        </div>
      

    </div>
  </aside>


        
      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2017</span>
  <span class="with-love">
    <i class="fa fa-user"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">cayun</span>

  
</div>


  <div class="powered-by">由 <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a> 强力驱动</div>



  <span class="post-meta-divider">|</span>



  <div class="theme-info">主题 &mdash; <a class="theme-link" target="_blank" href="https://github.com/iissnan/hexo-theme-next">NexT.Pisces</a></div>




        







        
      </div>
    </footer>

    

    

  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>









  












  
  
    <script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
  

  
  
    <script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  

  
  
    <script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
  

  
  
    <script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js?v=2.1.5"></script>
  


  


  <script type="text/javascript" src="/js/src/utils.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/motion.js?v=5.1.3"></script>



  
  


  <script type="text/javascript" src="/js/src/affix.js?v=5.1.3"></script>

  <script type="text/javascript" src="/js/src/schemes/pisces.js?v=5.1.3"></script>



  

  


  <script type="text/javascript" src="/js/src/bootstrap.js?v=5.1.3"></script>



  


  




	





  





  




  
    <script id="cy_cmt_num" src="https://changyan.sohu.com/upload/plugins/plugins.list.count.js?clientId=cyt6VLWhj"></script>
  









  





  

  
<script>
(function(){
    var bp = document.createElement('script');
    var curProtocol = window.location.protocol.split(':')[0];
    if (curProtocol === 'https') {
        bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';        
    }
    else {
        bp.src = 'http://push.zhanzhang.baidu.com/push.js';
    }
    var s = document.getElementsByTagName("script")[0];
    s.parentNode.insertBefore(bp, s);
})();
</script>


  
  

  
  
    <script type="text/x-mathjax-config">
      MathJax.Hub.Config({
        tex2jax: {
          inlineMath: [ ['$','$'], ["\\(","\\)"]  ],
          processEscapes: true,
          skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
        }
      });
    </script>

    <script type="text/x-mathjax-config">
      MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for (i=0; i < all.length; i += 1) {
          all[i].SourceElement().parentNode.className += ' has-jax';
        }
      });
    </script>
    <script type="text/javascript" src="//cdn.bootcss.com/mathjax/2.7.1/latest.js?config=TeX-AMS-MML_HTMLorMML"></script>
  


  

  

</body>
</html>
